package org.example.myleet.p524;

import java.util.List;

public class Solution {
    /**
     * 官方思路：排序 + 动态规划 + 双指针
     * 相对于暴力比较的思路，使用动态规划可以减少对于字符串s里面字符的搜寻
     */
    public String findLongestWord(String s, List<String> dictionary) {
        //排序，按长的优先，字典序小的优先，这样找到的第一个就是题目的要求的答案
        dictionary.sort((o1, o2) -> {
            if (o1.length() == o2.length()) {
                return o1.compareTo(o2);
            }
            return o2.length() - o1.length();
        });
        //dp[i][j]表示从第i个位置开始，下一个(j + 'a')的字母所处的索引位置
        int[][] dp = new int[s.length() + 1][26];
        for (int j = 0; j < 26; ++j) {
            //边界条件，s的最后位置，所有的字母下一个位置都是越界的地方
            dp[s.length()][j] = s.length();
        }
        for (int i = s.length() - 1; i >= 0; --i) {
            char sc = s.charAt(i);
            int sj = sc - 'a';
            for (int j = 0; j < 26; ++j) {
                //动态规划递推公式
                if (sj == j) {
                    //找到对应的字母，标记字母位置
                    dp[i][j] = i;
                } else {
                    //找不到对应的字母，则此位置下一个(j + 'a')的字母由下一个位置推导过来
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }
        for (String word : dictionary) {
            //还是双指针，分别对应s和word的第i个位置的字符
            int si = 0, wi = 0;
            while (wi < word.length()) {
                if (si >= s.length()) {
                    //超出，说明s找不到与word对应的子串
                    break;
                }
                char wc = word.charAt(wi);
                //找到word中对应字母的下一个位置
                int nextSi = dp[si][wc - 'a'];
                if (nextSi < s.length()) {
                    //找到s中对应word第i个字母的位置，wi指针前进，下一轮匹配下一个字母
                    ++wi;
                    if (wi == word.length()) {
                        //s中对应word的子串已经全部找到
                        return word;
                    }
                    //si在找到的字母下标的下一个开始
                    si = nextSi + 1;
                } else {
                    //超出，说明s找不到与word对应的子串
                    break;
                }
            }
        }
        //找不到
        return "";
    }

    /**
     * 暴力比较，使用双指针遍历字符串s做字符比较
     */
    public String findLongestWord2(String s, List<String> dictionary) {
        dictionary.sort((o1, o2) -> {
            if (o1.length() == o2.length()) {
                return o1.compareTo(o2);
            }
            return o2.length() - o1.length();
        });
        for (String word : dictionary) {
            int si = 0, wi = 0;
            while (wi < word.length()) {
                if (si >= s.length()) {
                    break;
                }
                char sc = s.charAt(si);
                char wc = word.charAt(wi);
                if (sc == wc) {
                    ++wi;
                    if (wi == word.length()) {
                        return word;
                    }
                }
                ++si;
            }
        }
        return "";
    }
}
